package sort.leetcode;

/**
 * 求数组的逆序对
 * @author yuisama
 * @date 2022/03/19 09:31
 **/
public class Num51_ArrNiXu {
    public int reversePairs(int[] nums) {
        return reversePairsHelper(nums,0,nums.length - 1);
    }

    /**
     * 传入一个数组nums，就可以求出在nums[l..r]上的逆序对的个数
     * @param nums
     * @param l
     * @param r
     * @return 此时nums[l...r] 逆序对的个数
     */
    private int reversePairsHelper(int[] nums, int l, int r) {
        if (l >= r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        // 先求出左区间的逆序对个数
        int left = reversePairsHelper(nums,l,mid);
        // 再求出右区间的逆序对个数
        int right = reversePairsHelper(nums,mid + 1,r);
        if (nums[mid] > nums[mid + 1]) {
            // 排序好的左右区间还存在逆序
            return merge(nums,l,mid,r) + left + right;
        }
        // 左右区间已经有序，整个集合也有序，整个集合的逆序对个数就是
        return left + right;
    }

    /**
     * 合并nums两个有序区间[l..mid] [mid + 1...r]
     * 返回合并过程中逆序对的个数
     * @param nums
     * @param l
     * @param mid
     * @param r
     * @return
     */
    private int merge(int[] nums, int l, int mid, int r) {
        int[] aux = new int[r - l + 1];
        // 合并过程中产生的逆序对个数
        int ret = 0;
        for (int i = 0; i < aux.length; i++) {
            aux[i] = nums[i + l];
        }
        int i = l;
        int j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 左区间已经合并完毕，放入右区间元素
                nums[k] = aux[j - l];
                j ++;
            }else if (j > r) {
                // 右区间已经合并完毕，放入左区间元素
                nums[k] = aux[i - l];
                i ++;
            }else if (aux[i - l] <= aux[j - l]) {
                // 左区间的元素 < 右区间元素，不构成逆序对
                nums[k] = aux[i - l];
                i ++;
            }else {
                // 右区间的元素 < 左区间的元素，构成逆序对
                // 此时逆序对的个数 = mid - i + 1
                ret += (mid - i) + 1;
                nums[k] = aux[j - l];
                j ++;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] nums = {7,5,6,4};
        Num51_ArrNiXu test = new Num51_ArrNiXu();
        int ret = test.reversePairs(nums);
        System.out.println(ret);
    }
}